package com.chapter4.graph.direct;

import java.util.Stack;

/**
 * 
* @ClassName: DirectedDFS 
* @Description: 有向图的深度优先搜索
* @author minjun
* @date 2015年3月1日 下午2:59:27 
*
 */
public class DirectedDFS {
	
	private boolean[] marked;
	
	private int[] edgeTo;
	
	private int s;
	
	public DirectedDFS(Digraph d,int s){
		this.s=s;
		marked=new boolean[d.V()];
		edgeTo=new int[d.V()];
		dfs(d,s);
	}

	/**
	 * 
	* @Title: dfs 
	* @Description: 深度优先搜索 
	* @param @param d
	* @param @param s    设定文件 
	* @return void    返回类型 
	* @throws
	 */
	private void dfs(Digraph d, int v) {
		marked[v]=true;
		for(int w:d.adj(v)){
			if(!marked[w]){
				edgeTo[w]=v;
				dfs(d, w);
			}
		}
	}
	
	/**
	 * 
	* @Title: hasPathTo 
	* @Description: 是否有可达路径 
	* @param @param v
	* @param @return    设定文件 
	* @return boolean    返回类型 
	* @throws
	 */
	public boolean hasPathTo(int v){
		return marked[v];
	}
	
	public Iterable<Integer> pathTo(int v){
		if(!marked[v]) throw new RuntimeException("不可达");
		
		Stack<Integer> path=new Stack<Integer>();
		for(int i=v;i!=s;i=edgeTo[i]){
			path.add(i);
		}
		path.add(s);
		return path;
	}
	
	public String path(int v){
		Stack<Integer> path=(Stack<Integer>)pathTo(v);
		StringBuilder sb=new StringBuilder();
		while(!path.isEmpty()){
			sb.append(path.pop()+"->");
		}
		int len =sb.length();
		if(sb.toString().endsWith("->")){
			sb.delete(len-2, len);
		}
		return sb.toString();
	}
}
